package com.itheima;

import org.junit.Test;

import java.util.*;

public class GreedyProblem {
    public int maxProfit(int[] prices) {
//        int n = prices.length;
//        int[] dp = new int[n];
//
//        dp[0] = 0;
//        for(int i = 1; i < n; i++) {
//            for(int j = 0; j < i; j++) {
//                if(prices[j] < prices[i]) {
//                    dp[i] = Math.max(dp[i], prices[i] - prices[j]);
//                }
//            }
//        }
//
//        return Arrays.stream(dp).max().getAsInt();
        int maxProfit = 0;
        int n = prices.length;
        int mn = prices[0];


        for(int i = 1; i < n; i++) {
            if(prices[i] < mn) {
                mn = prices[i];
            }
            maxProfit = Math.max(maxProfit, prices[i] - mn);
        }

        return maxProfit;
    }


    public boolean topic55(int[] nums) {
//        boolean res = false;
        int n = nums.length;

        int maxNum = 0;

        for(int i = 0; i < n - 1; i++) {
            if(maxNum >= i)
                maxNum = Math.max(maxNum, nums[i] + i);
        }


        return maxNum >= n - 1;
    }

    public int topic45(int[] nums) {
        int n = nums.length;
        int step = 0;
        int maxLen = 0;
        int end = 0;

        for(int i = 0; i < n - 1; i++) {
            maxLen = Math.max(maxLen, i + nums[i]);
            if(end == i) {
                end = maxLen;
                step++;

            }
        }
        return step;

    }

    public List<Integer> topic763(String s) {
        int n = s.length();

        Map<Character, Integer> map = new HashMap<>(); //记录出现的字母的最后位置

        for(int i = 0; i < n; i++) {
            map.put(s.charAt(i), Math.max(map.getOrDefault(s.charAt(i), 0), i));
        }

        List<Integer> res = new ArrayList<>();
        int end = 0;
        int prev = 0;
        for(int i = 0; i < n; i++) {
            end = Math.max(end, map.get(s.charAt(i)));
            if(end == i) {
                if(prev == 0) {
                    res.add(end - prev + 1);
                } else {
                    res.add(end - prev);
                }
                prev = end;
            }

        }
        return res;
    }


    @Test
    public void test() {
        System.out.println(topic763("ababcbacadefegdehijhklij"));
    }
}
